package LearnAlgorithm.c_递归and查找排序;

import java.util.HashMap;

import com.sun.java_cup.internal.runtime.virtual_parse_stack;

public class o非负乱序自然数编号数组求最小可分配id {
	public static void main(String[] args) {
		int[] arr = new int[] {2,1,3,4,6,5,9,8};
		//方式1：暴力
		//O(N^2)
		//从1开始依次探测每个自然数是否在数组中
		long before = System.currentTimeMillis();
		int forceSolution = forceSolution(arr);
		util.Util.duration(before);
		System.out.println(forceSolution);

		//方式2：先排序，再扫描对比
		//O(N*logN)
		//先快速排序，再逐个元素扫描是否有缺漏
		int[] arr2 = new int[] {2,1,3,4,6,5,9,8};
		long before2 = System.currentTimeMillis();
		int sortAfterScan = sortAfterScan(arr2, 0, arr2.length - 1);
		util.Util.duration(before2);
		System.out.println(sortAfterScan);
		
		//方式3：计数排序
		//O(N)
		//运用数组下标的意义；缺点是属于拿空间换时间
		int[] arr3 = new int[] {2,1,3,4,6,5,9,8};
		long before3 = System.currentTimeMillis();
		int countSortAndScan = countSortAfterScan(arr3);
		util.Util.duration(before3);
		System.out.println(countSortAndScan);
		
		//方式4：使用递归partition
		//O(N*logN)
		int[] arr4 = new int[] {2,1,3,4,6,5,9,8};
		long before4 = System.currentTimeMillis();
		int selectAndpartition = selectAndpartition(arr4, 0, arr4.length - 1);
		util.Util.duration(before4);
		System.out.println(selectAndpartition);
		
		for (int i = 0; i < arr4.length; i++) {
			System.out.print(arr4[i] + " ");
		}
	}
	
	public static int forceSolution(int[] arr) {
		int i = 1;
		while (true) {//1这个循环考虑到了数组是紧凑的情况
			int switchKey = 0;
			for (int j = 0; j < arr.length; j++) {
				if (arr[j] == i) {//3重复for循环比对会所有元素都不通过
					switchKey++;
					break;
				}
			}
			if (switchKey != 0) {
				i++;//2如果数组紧凑，最后加一操作会导致i=arr.length+1
			} else {
				return i;//4所以最后肯定会switchKey = 0，走这个判断分支
			}
		}
	}
	
	public static int sortAfterScan(int[] arr, int p, int r) {
		quickSort(arr, p, r);
		int i = 0;
		while (i < arr.length) {
			if (i + 1 != arr[i]) {
				return i + 1;//存在缺省，这个缺省位置就是要找的
			}
			i++;
		}
		return i + 1;//不存在缺省，那么就是数组长度+1
	}
	
	public static int countSortAfterScan(int[] arr) {
		int[] helper = new int[arr.length + 1];//这里+1的意义在于，为了空出helper[0],从[1]开始存元素，这样arr[i]的值就代表下标了
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] < arr.length + 1) {
				helper[arr[i]]++;
			}
		}
		for (int i = 1; i <= arr.length; i++) {//i从1开始，因为乱序数组是自然数，自然数从一开始；我们上面存数据也是从1索引开始；换句话说这里helper的下标和arr[i]的数值意义一样，理解了没有？
			if (helper[i] == 0) {//碰到了0，代表arr数组中不存在"helper下标i"这个数
				return i;
			}
		}
		return arr.length + 1;
	}
	
	public static int selectAndpartition(int[] arr, int p, int r) {
		if (p > r) {//这里是递归出口。为什么这样写去看蓝桥杯视频第三章3.13
			return p + 1;
		}
		int midIndex = p + ((r - p) >>> 1);//数组的下标的中值;midIndex - p + 1代表数组的下标的中值是数组的第几个元素
		int q = selectOfk(arr, p, r, midIndex - p + 1);//返回第(midIndex - p + 1)个元素的值
		if (q == -1) {//未找到第目标个元素
			return -1;
		} else if (q == midIndex + 1) {//如果第(midIndex - p + 1)个元素的值在数值上==“此元素的下标+1”，证明此元素左边所有元素稠密
			return selectAndpartition(arr, midIndex + 1, r);
		} else {//左侧稀疏
			return selectAndpartition(arr, p, midIndex - 1);
		}
	}
	
	public static int selectOfk(int[] arr, int p, int r, int k) {
		if (p < r) {
			int q = partition(arr, p, r);
			int locationOfk = q - p + 1;
			if (locationOfk == k) {
				return arr[q];
			} else if (k < locationOfk) {
				return selectOfk(arr, p, q - 1, k);
			} else {
				return selectOfk(arr, q + 1, r, k - locationOfk);
			}
		} else {
			return -1;
		}
	}
	
	public static void quickSort(int[] arr, int p, int r) {
		if (p < r) {
			if (r - p + 1 <= 8) {
				insertSort(arr, p, r);
			} else {
				int[] q = partitionThree(arr, p, r);
				quickSort(arr, p, q[0] - 1);
				quickSort(arr, q[1] + 1, r);
			}
		}
	}
	
	public static int partition(int[] arr, int p, int r) {
		int midIndex = getMedian(arr, p, r);
		int piovet = arr[midIndex];
		while (p <= r) {
			while (p <= r && arr[p] <= piovet) {
				p++;
			}
			while (p <= r && arr[r] > piovet) {
				r--;
			}
			if (p < r) {
				swap(arr, p, r);
			}
		}
		return r;
	}
	
	public static int[] partitionThree(int[] arr, int p, int r) {
		int e = p + 1;
		int sp = p + 1;
		int bigger = r;
		int midIndex = getMedian(arr, p, r);
		swap(arr, p, midIndex);
		int piovet = arr[p];
		int[] equalNumber = new int[2];
		while (sp <= bigger) {
			while (sp <= bigger && arr[sp] <= piovet) {
				if (arr[sp] < piovet && sp == e) {
					sp++;
					e++;
				} else if (arr[sp] < piovet && sp != e) {
					swap(arr, sp, e);
					sp++;
					e++;
				} else {
					sp++;
				}
			}
			while (sp <= bigger && piovet < arr[bigger]) {
				bigger--;
			}
			if (sp < bigger) {
				swap(arr, sp, bigger);
			}
		}
		swap(arr, p, e - 1);
		equalNumber[0] = e - 1;
		equalNumber[1] = bigger;
		return equalNumber;
	}
	
	public static int getMedian(int[] arr, int p, int r) {
		int size = r - p + 1;
		int groupSize = (size % 5 == 0) ? (size / 5) : ((size / 5) + 1);
		int indexOfMedians = 0;
		int[] medians = new int[groupSize];
		HashMap<Integer, Integer> medainsOfValueAndIndex = new HashMap<Integer, Integer>();
		for (int i = 0; i < groupSize; i++) {
			if (i == groupSize - 1) {
				insertSort(arr, p + (i * 5), r);
				medians[indexOfMedians] = arr[(p + (i * 5) + r) >>> 1];
				medainsOfValueAndIndex.put(arr[(p + (i * 5) + r) >>> 1], (p + (i * 5) + r) >>> 1);
			} else {
				insertSort(arr, p + (i * 5), p + (i * 5) + 4);
				medians[indexOfMedians++] = arr[p + (i * 5) + 2];
				medainsOfValueAndIndex.put(arr[p + (i * 5) + 2], p + (i * 5) + 2);
			}
		}
		insertSort(medians, 0, groupSize - 1);
		return medainsOfValueAndIndex.get(medians[(groupSize - 1) >>> 1]);
	}
	
	public static void insertSort(int[] arr, int p, int r) {
		int before_i = 0;
		int value_i = 0;
		for (int i = p + 1; i <= r; i++) {
			before_i = i - 1;
			value_i = arr[i];
			while (before_i > p - 1 && arr[before_i] > value_i) {
				arr[before_i + 1] = arr[before_i--];
			}
			arr[before_i + 1] = value_i;
		}
	}
	
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
